'''
Project Euler Problem 3: https://projecteuler.net/problem=3

Largest prime factor

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143?
'''

# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = Thonny Python3.8
@creat_time = 2022/5/3
'''

import math


def notPrime(n:int) -> bool:
    if n<2:
        return True
    
    if n == 2:
        return False
      
    for i in range(2,int(math.sqrt(n))+1):
        if n%i == 0:
            return i
        
    return False


'''
def primes(maxNum: int) -> list:
    if maxNum < 2:
        return []
    
    ps = [2]
    rest = [x for x in range(3,maxNum+1) if x%2 != 0]
    
    while rest:
        ps.append(rest[0])
        rest = [x for x in rest if x%rest[0] != 0]
    
    return ps
'''    

def largest_prime_factor(n: int = 600851475143) -> int:
    '''
    the largest prime factor of the number
    
    >>> largest_prime_factor(10)
    5
    >>> largest_prime_factor(99)
    11
    >>> largest_prime_factor(2)
    2
    >>> largest_prime_factor(1)
    1
    '''
    if n==1:
        return 1
    
    if n==2:
        return n
   
    factor = notPrime(n)
    
    if factor >= 2:
        while n%factor == 0:
            # print('{} / {} = {}'.format(n,factor,n//factor))
            n = n//factor
        
        return max(factor, largest_prime_factor(n))
    else:
        return n
        



if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose = True)
    
    print(f"{largest_prime_factor() = }")

